<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>动态规划编辑距离</title>
    </head>
    <body>
        <p>
            给你两个单词 wo rd 1 和 wo rd 2，请你计算出将 wo rd 1 转换成 wo rd 2
            所使用的最少 操作数 。 你可以对一个单词进行如下三种操作：
        </p>
        <p>你可以对一个单词进行如下三种操作：</p>
        <ul>
            <li>插入一个字符</li>
            <li>删除一个字符</li>
            <li>替换一个字符</li>
        </ul>
        <h4>示例 1：</h4>
        <div>
            <p>输入：word 1 = " horse", word 2 = "ros"</p>
            <p>输出：3</p>
            <div>
                解释：
                <p>horse -> rorse (将 ' h ' 替换为 'r')</p>
                <p>rorse -> rose(删除 'r')</p>
                <p>rose -> ros (删除 ' e ')</p>
            </div>
            总有共3步
        </div>
        <h4>示例 2：</h4>
        <div>
            <p>输入：word1 = "intention", word 2 = "execution"</p>
            <p>输出：5</p>
            <div>
                解释：
                <p>intention -> inention (删除 ' t ')</p>
                <p>inention -> enention (将 ' i ' 替换为 ' e ')</p>
                <p>enention -> exention (将 ' n ' 替换为 ' x ')</p>
                <p>exention -> exection (将 ' n ' 替换为 ' c ')</p>
                <p>exection -> execution (插入 ' u ')</p>
            </div>
            总有共5步
        </div>

        <section>
            <h2>分析</h2>
            <p>1.如果想把word1变为word2，对于word1的操作我们有3种方式：</p>
            <p>删除一个字符</p>
            <p>添加一个字符</p>
            <p>修改一个字符</p>
            <div>这就好比对数据库的增删改查一样，不过这里没有查找。</div>
            <div>
                我们用
                <mark
                    >dp[i][j]表示把word1的前i个字符变为word2的前j个字符所需要的最少编辑距离，</mark
                >
                这里要分两种情况
                <div>
                    1 ，当word1[i]==word2[j] ： 也 就 是 说 word1 的 第 i 个 字
                    符 和 word2 的 第 j 个 字 符 相
                    等，我们不需要修改word1的第i个字符，所以这时dp[i][j]=dp[i
                    -1][j -1]。
                </div>
                <div>
                    2，当word1[i]!=word2[j] ： 也 就 是 说 word1 的 第 i 个 字
                    符 和 word2 的 第 j 个 字 符 不 相
                    等。这时我们可以有3种操作来计算dp[i][j];
                    <ol>
                        <li>
                            删，dp[i -1][j]：表示的是word1的前i
                            -1个字符和word2的前j个字符的最小编辑 距 离 ， 在
                            dp[i][j] 中 我 们 只 需 要 把 word1 中 第 i 个 字 符
                            删 除 就 是 dp[i -1][j] ， 所 以 dp[i][j]=dp[i
                            -1][j]+1。
                        </li>
                        <li>
                            增，dp[i][j
                            -1]：表示的是word1的前i个字符和word2的前j
                            -1个字符的最小编辑
                            距离，在dp[i][j]中我们只需要把word2中的第j个字符删除就是dp[i][j
                            -1]，所以 dp[i][j]=dp[i][j
                            -1]+1。（注：我们这一步明明是增，但这里为什么是删，因为
                            我们这里删的是word2 的字符，增和删是相对的，word2
                            字符的删除也可以认为 是 word1 字 符 的 添 加 ， 举
                            个 例 子 ， 比 如 word1="a" ， word2="ab" ， 我 们
                            在
                            word1中添加一个b或者在word2中删除一个b，最短编辑距离都是一样的）
                        </li>
                        <li>
                            改 ， dp[i -1][j -1] ： 表 示 的 是 word1 的 前 i -1
                            个 字 符 和 word2 的 前 j -1 个 字 符 的 最
                            小编辑距离，我们只需要把word1的第i个字符修改为word2的第j个字符就可以求
                            出dp[i][j]，所以dp[i][j]=dp[i -1][j -1]+1。
                        </li>
                    </ol>

                    <div>
                        <div>上面三种情况我们要选最小的，所以递推公式</div>
                        <div>1，当word1[i]==word2[j]：</div>
                        <mark>dp[i][j]=dp[i -1][j -1]</mark>
                        <div>2，当word1[i]!=word2[j]：</div>
                        <mark
                            >dp[i][j]=min{dp[i -1][j-1]，dp[i
                            -1][j],dp[i][j-1]}+1</mark
                        >
                        <div>边界条件：</div>
                        <div>
                            如果word1为空，我们要把word1变为word2就是不停的插入，
                        </div>
                        <div>
                            如果word2为空，我们要把word1变为word2就是不停的删除。
                        </div>
                    </div>
                </div>
            </div>
        </section>
    </body>
    <script>
        // 代码实现
        function minDistance(word1, word2) {
            let len1 = word1.length;
            let len2 = word2.length;

            // 1. 如果有一个是空字符串，直接返回另外一个字符串的长度
            if (len1 * len2 === 0) {
                return len1 + len2;
            }
            var dp = [];
            for (let i = 0; i < len1 + 1; i++) {
                dp[i] = [];
                for (let j = 0; j < len2 + 1; j++) {
                    dp[i][j] = 0;
                }
            }

            for (let i = 0; i <= len1; i++) {
                dp[i][0] = i; // 这里我们理解为 word1的删除操作
            }

            for (let j = 0; j <= len2; j++) {
                dp[0][j] = j; // 边界条件：相当于 word1的添加操作
            }

            for (let i = 1; i <= len1; i++) {
                for (let j = 1; j <= len2; j++) {
                    // 如果word1 的第 i - 1 个 和 word2的第 j - 1个相等，我们可以直接替换操作，得到
                    if (word1.charAt(i - 1) === word2.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        dp[i][j] =
                            Math.min(
                                Math.min(dp[i - 1][j], dp[i][j - 1]),
                                dp[i - 1][j - 1]
                            ) + 1;
                    }
                }
            }
            return dp[len1][len2];
        }
        // 开始测试
        var word1 = "horse",
            word2 = "ros";
        console.log(minDistance(word1, word2));
        var word1 = "intention",
            word2 = "execution";
        console.log(minDistance(word1, word2));
    </script>
    <!-- 代码优化 -->
    <!-- 我们看到虽然dp是二维数组，但我们计算的时候每个元素只和他的左边，上边，左上角 的3个值有关，所以这里我们还可以优化一下，使用一维数组，我们看下代码 -->
    <script>
        function minDistance_good(word1, word2) {
            var len1 = word1.length,
                len2 = word2.length;
            if (len1 * len2 === 0) {
                return len1 + len2;
            }
            var dp = [0];
            for (let i = 1; i < len2 + 1; i++) {
                dp[i] = i;
            }
            var last = 0;
            for (let i = 1; i <= len1; i++) {
                last = dp[0];
                dp[0] = i;
                for (let j = 1; j <= len2; j++) {
                    var temp = dp[j];
                    if (word1.charAt(i - 1) === word2.charAt(j - 1)) {
                        dp[j] = last;
                    } else {
                        dp[j] = Math.min(Math.min(dp[j - 1], dp[j]), last) + 1;
                    }
                    last = temp;
                }
            }
            return dp[len2];
        }
        var word1 = "horse",
            word2 = "ros";
        console.log(minDistance_good(word1, word2));
        var word1 = "intention",
            word2 = "execution";
        console.log(minDistance_good(word1, word2));
    </script>
</html>
